package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-18 16:14
 * @Description: BombEnem$361-轰炸敌人-https://leetcode-cn.com/problems/bomb-enemy/
 */
public class BombEnem {

	/**
	 *
	 * 想象一下炸弹人游戏，在你面前有一个二维的网格来表示地图，网格中的格子分别被以下三种符号占据：
	 *
	 * 'W' 表示一堵墙
	 * 'E' 表示一个敌人
	 * '0'（数字 0）表示一个空位
	 *
	 * 请你计算一个炸弹最多能炸多少敌人。
	 *
	 * 由于炸弹的威力不足以穿透墙体，炸弹只能炸到同一行和同一列没被墙体挡住的敌人。
	 *
	 * 注意：你只能把炸弹放在一个空的格子里
	 *
	 * 示例:
	 *
	 * 输入: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
	 * 输出: 3
	 * 解释: 对于如下网格
	 *
	 * 0 E 0 0
	 * E 0 W E
	 * 0 E 0 0
	 *
	 * 假如在位置 (1,1) 放置炸弹的话，可以炸到 3 个敌人
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/bomb-enemy
	 *
	 * 【题目分析】
	 * * 每个炸弹可以向四个方向传播爆炸力
	 * * 可以先分析一个方向，然后举一反三
	 * * 即如果在一个空地上放一个炸弹，最多向上能炸死多少敌人
	 * * 可以直接枚举，即向上枚举到碰到墙为止，
	 *      时间复杂度O（MN*M）
	 *   使用动态规划思想加速
	 * step 1:确定状态
	 *   先确定状态，假设有敌人或有墙的格子也能放炸弹
	 *   -有敌人的格子：格子里的敌人被查瑟，并继续向上爆炸
	 *   -有墙的各自：炸弹不能炸死任何敌人
	 *   所以在（i,j）格放一个炸弹，它向上能炸死的敌人数是：
	 *      (i,j)格为空地：(i-1,j)格向上能炸死的敌人数
	 *      (i,j)格为敌人：(i-1,j)格向上能炸死的地人数+1
	 *      (i,j)格为墙：0
	 *
	 *   子问题：
	 *      需要知道（i-1,j）格放一个炸弹向上能炸死的敌人数
	 *      原来要求(i,j)格放一个炸弹能向上炸死的敌人数
	 *
	 *   状态：Up[i][j]表示(i,j)格放一个炸弹能向上炸死的敌人数
	 *
	 * step2:转移方程
	 *      设Up[i][j]表示(i,j)格放一个炸弹能向上炸死的敌人数
	 *
	 *                  Up[i-1][j],如果（i,j）格是空地
	 *      Up[i][j]=   Up[i-1][j]+1,如果（i,j）格是敌人
	 *                  0，如果(i,j)是墙
	 *
	 * step3:初始条件和边界情况
	 *
	 *      初始条件：第0行的Up值和格字内容相关
	 *          -Up[0][j] = 0,如果(0,j)格不是敌人
	 *          -Up[0][j] = 1,如果(0,j)格式敌人
	 *
	 * step4:计算顺序
	 *      Up[0][0],Up[0][1],...,Up[0][n-1]
	 *      Up[1][0],Up[1][1],...,Up[1][n-1]
	 *      ...
	 *      Up[m-1][0],Up[m-1][1],...,Up[m-1][n-1]
	 *
	 *      时间复杂度：O(MN),空间复杂度：O(MN)
	 *
	 * 综上：Up[i][j]表示如果（i,j）放一个炸弹向上可以最多炸死多少敌人
	 *      一共四个方向
	 *          可以类似地计算Down[i][j],Left[i][j],Right[i][j],注意计算顺序会发生改变。
	 *
	 *      (i,j)如果是空地，放一个炸弹最多炸死的敌人数是：
	 *          Up[i][j]+Down[i][j]+Left[i][j]
	 *       取最大值即可
	 *       时间复杂度和空间复杂度仍然是O(MN)
	 *
	 *
	 *
	 *
	 *
	 */

	public int maxKilledEnemies(char[][] grid) {
		if(grid==null||grid.length==0||grid[0].length==0){
			return 0;
		}

		int m = grid.length;
		int n = grid[0].length;


		// 仅开辟一个数组，反复使用
		int[][] f = new int[m][n];
		int[][] res = new int[m][n];

		int i,j;
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				// 在表格(i,j)的位置，放一个炸弹可以杀死多少敌人，
				// 没有必要开辟四个数组，分别计算四个方向的杀敌数，直接累加即可
				// 算一个加一个
				res[i][j] = 0;
			}
		}

		//上方向杀死的敌人数
		for (i = 0;  i< m; ++i) {
			for (j  = 0; j < n ; ++j) {
				// 是墙壁，否决
				if(grid[i][j]=='W'){
					f[i][j] = 0;
				}
				else{
					f[i][j] = 0;
					// 如果是敌人，赚一个
					if(grid[i][j]=='E'){
						f[i][j] = 1;
					}

					// 如果有上一行，将上一行的值加过来
					if(i-1 >= 0){
						f[i][j] +=f[i-1][j];
					}
				}
				res[i][j] += f[i][j];
			}
		}

		// 下方向，从下向上计算，因为需要知道向下每格可以炸多少，所以先算下面的格子炸多少
		for (i = m-1;  i>=0; --i) {
			for (j  = 0; j < n ; ++j) {
				// 是墙壁，否决
				if(grid[i][j]=='W'){
					f[i][j] = 0;
				}
				else{
					f[i][j] = 0;
					// 如果是敌人，赚一个
					if(grid[i][j]=='E'){
						f[i][j] = 1;
					}

					// 如果有下一行，将下一行的值加过来
					if(i+1<m){
						f[i][j] +=f[i+1][j];
					}
				}
				res[i][j] += f[i][j];
			}
		}

		//左方向杀死的地人数
		for (i = 0;  i<m; ++i) {
			for (j  = 0; j < n ; ++j) {
				// 是墙壁，否决
				if(grid[i][j]=='W'){
					f[i][j] = 0;
				}
				else{
					f[i][j] = 0;
					// 如果是敌人，赚一个
					if(grid[i][j]=='E'){
						f[i][j] = 1;
					}

					// 如果有下一行，将下一行的值加过来
					if(j-1 >= 0){
						f[i][j] +=f[i][j-1];
					}
				}
				res[i][j] += f[i][j];
			}
		}

		//右方向杀死的地人数
		for (i = 0;  i<m; ++i) {
			for (j  = n-1; j >= 0 ; --j) {
				// 是墙壁，否决
				if(grid[i][j]=='W'){
					f[i][j] = 0;
				}
				else{
					f[i][j] = 0;
					// 如果是敌人，赚一个
					if(grid[i][j]=='E'){
						f[i][j] = 1;
					}

					// 如果有下一行，将下一行的值加过来
					if(j+1 < n){
						f[i][j] +=f[i][j+1];
					}
				}
				res[i][j] += f[i][j];
			}
		}

		int result = 0;
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if(grid[i][j]=='0'){
					if(res[i][j]>result){
						result = res[i][j];
					}
				}
			}
		}

		return result;
	}
	public static void main(String[] args) {
		char[][] grid = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}};
		BombEnem instance = new BombEnem();
		System.out.println(instance.maxKilledEnemies(grid));
	}
}
